package com.practice.recursive;

/**
 * Given a number N, print all the ways (combinations) to represent 
 * the number from the given set of integers.
 * 
 * Given set is {2,3,7,8,9} and given number N = 7, then the combinations are:
 * 7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
 * 
 */
public class SplitNumber {
	private int count;
	
	public int countWays(int sum, int[] numbers) {
		int N = sum/numbers[0] + 1;
		int[] a = new int[N];
		count = 0;
		for (int i=0; i<numbers.length; i++) {
			a[0] = numbers[i];
			split(sum, numbers, a, i, 1, a[0]);
		}
		return count;
	}
	
	private void split(int sum, int[] numbers, int[] a, int low, int len, int curSum) {
		if (curSum == sum) {
			count++;
//			for (int i=0; i<len; i++) {
//				System.out.print(a[i] + " ");
//			}
//			System.out.println();
			return;
		}
		
		for (int i=low; i<numbers.length; i++) {
			if (curSum + numbers[i] > sum) break;
			a[len] = numbers[i];
			split(sum, numbers, a, i, len+1, curSum+numbers[i]);
		}
	}
}
